
#include <stdio.h>
/*
typedef struct ListNode{
    int val;
    struct ListNode*next;
}ListNode;
ListNode* partition(ListNode* pHead, int x)
{
    if(pHead==NULL||pHead->next==NULL)//如果链表为空或者只有一个元素
        return pHead;

    ListNode *lesslist=NULL;//小于x的节点链表
    ListNode *lesstail=NULL;//小于x节点链表表尾

    ListNode *cur=pHead;//遍历原链表
    ListNode *pre=NULL;//当前节点的前驱

    //遍历链表节点，挑选比x小的节点出来组成新的链表
    //最后连接起来
    while (cur!=NULL)
    {
        ListNode *next=cur->next;//当前节点的后继节点
        if(cur->val<x)
        {
            if(lesslist==NULL)//小于x的链表未创建
            {
                lesslist=lesstail=cur;
            }
            else//创建了
            {
                lesstail->next=cur;
                lesstail=cur;
            }
            //从原链表中删除该节点
            if(pre==NULL)//第一个节点
            {
                pHead=next;//更新原链表头节点
            }
            else
            {
                pre->next=next;
            }
            cur->next=NULL;
        }
        else//当前节点不是小于x的
        {
            pre=cur;
        }
        cur=next;//cur向后移动
    }
    if(lesstail==NULL)//没有小于x的节点
        return pHead;
    else
    {
        lesstail->next=pHead;
        return lesslist;
    }
}*/
